package com.demo06.qsort;

/**
 * @Author: root
 * @Date: 2018/11/14 23:27
 */
public class QuickSort2 {
    public static void main(String[] args) {
        int[] arr = {10, 20, 7, 15, 0, 19, 1, 17, 30, 18, -1, 21};
        qSort(arr, 0, arr.length - 1);
        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println();
    }

    private static void qSort(int[] arr, int start, int end) {

        if (start < end) {
            int i = start, j = end;
            int x = arr[start];
            while (i < j) {
                //从右向左扫描
                while (i < j && x <= arr[j]) {
                    j--;
                }
                if (i < j) {
                    arr[i++] = arr[j];
                }
                //从左向右扫描
                while (i < j && x > arr[i]) {
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
            arr[i] = x;
            qSort(arr, start, i - 1);
            qSort(arr, i + 1, end);
        }
    }
}
